/* author: Rainboy email: rainboylvx@qq.com  time: 2022年 07月 18日 星期一 20:07:44 CST */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5,maxe = 1e6+5; //点与边的数量

int n,m;
/* 定义全局变量 */

struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){	//构造函数
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }
    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }
    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    void add2(int u,int v,int w=0){
        add(u,v,w);
        add(v,u,w);
    }
    edge& operator[](int i){
        return e[i];
    }
    void sort(){
        std::sort(e,e+edge_cnt,[](edge &e1,edge& e2){ return e1.w < e2.w; });
    }
} e;



template<std::size_t size> 
struct Tarjan {
    
private:
    int dfn[size],low[size],color[size],dfn_cnt,color_cnt;
    int stack[size],shead;
    bool in_stack[size];
    inline int pop() { 
        int t = stack[--shead];
        in_stack[t] = 0;
        return t;
    }
    inline void push(int a) { 
        in_stack[a] = 1;
        stack[shead++] = a;
    }

public:
    Tarjan() :dfn_cnt(0), color_cnt(0), shead(0),in_stack(0)
    {}

    void work(linkList & e,int u = 1){
        dfn[u] = low[u] = ++dfn_cnt;
        push(u);
        for(int i = e.h[i] ; i!=-1;i= e[i].next ) {
            int v = e[i].v;
            if(!dfn[v]) { //没有访问过
                work(e,v);
                low[u] = min(low[u],low[v]);//更新low
            }
            else if( in_stack[v]) { //反祖边,节点v在栈内
                low[u] = min(low[u],low[v]);//更新low
            }
        }
        if( dfn[u] == low[u]) {
            color_cnt++;
            int t = -1;
            do {
                t = pop();
                color[t] = color_cnt;
            }while( t !=u);
        }
    }

    //某个点的强连通分量的编号
    int get_color(int a) { return color[a];}
    //两个点是否是同一个强连通分量
    bool is_same_color(int a,int b) { return color[a] == color[b]; }

    //得到强连通分量的数量
    int color_size() { return color_cnt;}

    //得到某个强连通分量的所有点
    //a 颜色,强连通分量编号
    //n 一共有多少个点
    std::vector<int> get_color_node(int a,int n){
        std::vector<int> v;
        for(int i = 1;i <=n;i++) {
            if( color[i] == a) v.push_back(i);
        }
        return v;
    }

};

int main(int argc,char * argv[]){
    
    return 0;
}
